This invention relates to backing up and/or restoring objects (such as in the form of files) on an object storage system (such as a file system). File systems are typically backed up to a backup storage on a regular basis, and in performing backups or retrievals, it is desirable to quickly locate a backup file. Information about backup files may be stored in an index for rapid searching, so that the backup system does not have to search the entire backup storage. A set of data being backed up in a backup operation (e.g., a grouping of files and/or directories to be backed up) may be referred to herein as a “saveset”.
The index, sometimes referred to herein as “client file index”, stores information about the savesets. When it is desired to determine what has been backed up, such as during retrieval, the index may be used to facilitate lookup. However, storage systems often contain large numbers of objects, and it would not be unusual for a storage system to contain hundreds of thousands, or millions, of objects. Even with the use of an index, a straightforward search of the index for backup objects can be unwieldy and slow.
There is a need, therefore, for an improved method, article of manufacture, and apparatus for efficiently locating backup files.